/************************************
 * Author：Zhaoqiang Shen
 * Date：2018.03.13
 *《算法导论》（中文第三版）搜索相关的code
 ************************************/
#include <iostream>
#include <vector>

using std::cout;
using std::vector;

int linearSearch(const vector<int> &A, int v) {
    // Ex 2.1-2
    for (size_t i=0; i<A.size(); ++i)
        if (v == A[i])
            return i;
    return -1;
}

int binarySearch(const vector<int> &A, int p, int q, int v) {
    // Ex 2.3-5
    if (p>q) return -1;

    int mid=(p+q)/2;
    if (v==A[mid])
        return mid;
    else if (v<A[mid])
        return binarySearch(A, p, mid-1, v);
    else
        return binarySearch(A, mid+1, q, v);
}

int binarySearch_drive(const vector<int> &A, int v) {
    return binarySearch(A, 0, A.size()-1, v);
}

void test() {
    vector<int> v1={0};
    vector<int> v2={1,3,5,7,9};

    cout << "Test Array1: ";
    for (int v: v1) {
        cout << v << " ";
    }
    cout << std::endl;

    int i;

    cout << "  Search 0:"<< std::endl;
    cout << "    LINEAR-SEARCH: ";
    i = linearSearch(v1, 0);
    cout << i << std::endl;
    cout << "    BINARY-SEARCH: ";
    i = binarySearch_drive(v1, 0);
    cout << i << std::endl;

    cout << "  Search -1:"<< std::endl;
    cout << "    LINEAR-SEARCH: ";
    i = linearSearch(v1, -1);
    cout << i << std::endl;
    cout << "    BINARY-SEARCH: ";
    i = binarySearch_drive(v1, -1);
    cout << i << std::endl;

    cout << "  Search 2:"<< std::endl;
    cout << "    LINEAR-SEARCH: ";
    i = linearSearch(v1, 2);
    cout << i << std::endl;
    cout << "    BINARY-SEARCH: ";
    i = binarySearch_drive(v1, 2);
    cout << i << std::endl;

    cout << "Test Array2: ";
    for (int v: v2) {
        cout << v << " ";
    }
    cout << std::endl;

    cout << "  Search 5:"<< std::endl;
    cout << "    LINEAR-SEARCH: ";
    i = linearSearch(v2, 5);
    cout << i << std::endl;
    cout << "    BINARY-SEARCH: ";
    i = binarySearch_drive(v2, 5);
    cout << i << std::endl;

    cout << "  Search 1:"<< std::endl;
    cout << "    LINEAR-SEARCH: ";
    i = linearSearch(v2, 1);
    cout << i << std::endl;
    cout << "    BINARY-SEARCH: ";
    i = binarySearch_drive(v2, 1);
    cout << i << std::endl;

    cout << "  Search 9:"<< std::endl;
    cout << "    LINEAR-SEARCH: ";
    i = linearSearch(v2, 9);
    cout << i << std::endl;
    cout << "    BINARY-SEARCH: ";
    i = binarySearch_drive(v2, 9);
    cout << i << std::endl;

    cout << "  Search 2:"<< std::endl;
    cout << "    LINEAR-SEARCH: ";
    i = linearSearch(v2, 2);
    cout << i << std::endl;
    cout << "    BINARY-SEARCH: ";
    i = binarySearch_drive(v2, 2);
    cout << i << std::endl;

    cout << "  Search -1:"<< std::endl;
    cout << "    LINEAR-SEARCH: ";
    i = linearSearch(v2, -1);
    cout << i << std::endl;
    cout << "    BINARY-SEARCH: ";
    i = binarySearch_drive(v2, -1);
    cout << i << std::endl;

    cout << "  Search 11:"<< std::endl;
    cout << "    LINEAR-SEARCH: ";
    i = linearSearch(v2, 11);
    cout << i << std::endl;
    cout << "    BINARY-SEARCH: ";
    i = binarySearch_drive(v2, 11);
    cout << i << std::endl;
}

int main() {
    test();

    int n;
    cout << "Array Size:> ";
    std::cin >> n;

    int v;
    vector<int> A;
    cout << "Input Array:> ";
    for (int i=0; i<n; ++i) {
        std::cin >> v;
        A.push_back(v);
    }

    int v2;
    cout << "Search for?> ";
    std::cin >> v2;

    if (!A.empty()) {

        int i;
        cout << "LINEAR-SEARCH: ";
        i = linearSearch(A, v2);
        cout << i << std::endl;

        cout << "BINARY-SEARCH: ";
        i = binarySearch_drive(A, v2);
        cout << i << std::endl;

        return 0;
    } else
        return 1;
}